package org.example.graph_theory;

import java.util.Arrays;

public class The_area_that_is_surrounded {
    public static void main(String[] args) {
        //被围绕的区域

        //给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
//        {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        char[][] board = {
                {'X','O','X','O','X','O'},
                {'O','X','O','X','O','X'},
                {'X','O','X','O','X','O'},
                {'O','X','O','X','O','X'}
        };
        solve(board);
    }

    public static void solve(char[][] board) {
        if (board.length >=3 && board[0].length>=3){
            for (int i = 0; i < board[0].length; i++) {
                dfs(board,0,i);
            }
            for (int i = 0; i < board[board.length-1].length; i++) {
                dfs(board, board.length-1,i );
            }
            for (int i = 0; i < board.length; i++) {
                dfs(board,i,0);
            }
            for (int i = 0; i < board.length; i++) {
                dfs(board,i, board[0].length-1);
            }

            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] == 'O'){
                        board[i][j] = 'X';
                    } else if (board[i][j] == 'Y') {
                        board[i][j] = 'O';
                    }
                }
            }

        }
        System.out.println(Arrays.deepToString(board));
    }

    public static void dfs(char[][] board,int i,int j){
        if (i<0 || i>= board.length || j<0 || j>=board[i].length || board[i][j] == 'X' || board[i][j] == 'Y') return;
        board[i][j] = 'Y';
        dfs(board,i-1,j);
        dfs(board,i+1,j);
        dfs(board,i,j-1);
        dfs(board,i,j+1);
    }
}
